Merge sort
列を細かい列にわけ、先頭を比較しならがmergeしていき、徐々に要素数を戻していく
個々の列はmergeされるまで独立しているので並列に計算できる
命名
sortされた細かい列をmergeしながらsortしていくから
計算量
平均計算時間: $ O(n\log{n})
bestのところの「typical」と「natural variant」ってどういう意味 #?? アルゴリズム
列を2等分する
各列で
含まれるデータが1個ならそれを返す
2個以上なら再帰
2つのsort済みの列を先頭を比較しながらmerge
可視化
https://upload.wikimedia.org/wikipedia/commons/c/cc/Merge-sort-example-300px.gif
8要素の列を、2要素の列に分ける
各「2要素の列」内でsortする
2つの「2要素の列」を先頭を比較しながらmerge
2つの「4要素の列」を先頭を比較しながらmerge
https://www.youtube.com/watch?v=ZRPoEKHXTJg
コード例
このコードは宣言的でやっていることが明確でわかりやすいが効率的ではない
Listを2分割する際(splitAtの部分)で($ O(1)ではなく)$ O(n)かかる
code:hs
msort [] = []
msort xs = merge (msort l) (msort r)
where
(l,r) = splitAt (length xs div 2) xs
merge :: Ord a => a -> a -> a merge xs [] = xs
merge [] ys = ys
merge xl@(x:xs) yl@(y:ys)
| x < y = x : merge xs yl
| otherwise = y : merge xl ys
bottomup版
code:hs
msort [] = []
msort xs = go $ map (: []) xs
where
go xs = go $ pairs xs
pairs (a:b:t) = merge a b : pairs t
pairs t = t
最初に[[5],[3],[2],[4],[1]]のような二重リストを作った後に、
先頭の2つのリストから順々にmergeしていき、[[3,5],[2,4],[1]]を作って、
これに対して再びgoを適用して、を繰り返す
手続的な実装
実際に計測してみたらどうなるんだろう
前者はsplitAtの計算を食うけど、上手く書けば並行処理し速くなりそうな気もするけどmrsekut.icon
派生とか
長所と短所
参考